<!DOCTYPE html>
<html lang="en">
<head>
        <meta charset="utf-8" />
        <title>chapter11</title>
        <link rel="stylesheet" href="/theme/css/main.css" />

        <!--[if IE]>
            <script src="http://html5shiv.googlecode.com/svn/trunk/html5.js"></script>
        <![endif]-->
</head>

<body id="index" class="home">
        <header id="banner" class="body">
                <h1><a href="/">PythonTutorials </a></h1>
                <nav><ul>
                    <li class="active"><a href="/category/cpp.html">cpp</a></li>
                    <li><a href="/category/python.html">python</a></li>
                </ul>
                </nav>
        </header><!-- /#banner -->
<section id="content" class="body">
  <article>
    <header>
      <h1 class="entry-title">
        <a href="/chapter11.html" rel="bookmark"
           title="Permalink to chapter11">chapter11</a></h1>
    </header>

    <div class="entry-content">
<footer class="post-info">
        <span>Mon 06 April 2020</span>
<span>| tags: <a href="/tag/cpp.html">cpp</a><a href="/tag/progarmming.html">progarmming</a></span>
</footer><!-- /.post-info -->      <h1>线性查找</h1>
<div class="highlight"><pre><span></span>int lineSearch(long num[],int x,int n)//线性查找
{
    for (int i=0;i&lt;n;i++)
    {
        if (num[i]==x)
            {
                return 1;
            }
    }
    return -1;
}
</pre></div>


<h1>二分法查找</h1>
<div class="highlight"><pre><span></span>int BinarySearch(long num[],int x,int n)//假设数组升序排序
{
    int low = 0,high = n-1,mid;
    while(low &lt;=high)//区间存在
    {
        mid=(high+low)/2;//mid = low +(high-low)/2;方知数值溢出。分治思想的完美体现
        if(x&gt;num[mid])
        {
            low=mid+1;
        }
        else if(x&lt;num[mid])
        {
            high=mid-1;
        }
        else
        {
            return mid; //返回下标位置
        }
    }

    return -1;
}
</pre></div>


<h1>交换排序</h1>
<div class="highlight"><pre><span></span>void SwithSort(int score[],int n)//升序排列
{
    int temp;
    for(int i=0;i&lt;n-1;i++)
        for(int j=j+1;j&lt;n;j++)
        {
            if(score[i]&gt;score[j])
                temp=score[i];
                score[i]=score[j];
                score[j]=temp;
        }
}
</pre></div>


<h1>选择排序</h1>
<div class="highlight"><pre><span></span>void SelectSort(int score[],int n)
{
    int temp,k,i,j;
    for(i=0;i&lt;n-1;++i)
    {
                k=i;
        for(j=0;j&lt;n;j++)
        {
            if(score[j]&lt;score[i])
                k=j;
        }
        if(k!=i)
        {
            temp=score[k];
            score[k]=score[j];
            score[j]=temp;
        }
    }       
}
</pre></div>


<h1>冒泡排序</h1>
<div class="highlight"><pre><span></span>void BubbleSort(int score[],int n)
{
    int i,j,temp;
    for(i=0;i&lt;n-1;i++)
    {
        for(j=1;j&lt;n-i;j++) //i为已经排好序的元素
        {
            if(score[j]&lt;score[j-1])// j从1开始
            {
                temp=score[j];
                score[j]=score[j-1];
                score[j-1]=temp;
            }
        }
    }
}
</pre></div>


<h1>完整案例</h1>
<div class="highlight"><pre><span></span><span class="cp">#include</span> <span class="cpf">&lt;stdio.h&gt;</span><span class="cp"></span>
<span class="cp">#define N 40</span>
<span class="kt">int</span> <span class="nf">ReadScore</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">score</span><span class="p">[]);</span>
<span class="kt">int</span> <span class="nf">lineSearch</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">n</span><span class="p">);</span><span class="c1">//线性查找</span>
<span class="kt">int</span> <span class="nf">BinarySearch</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">n</span><span class="p">);</span><span class="c1">//二分查找</span>
<span class="kt">void</span> <span class="nf">SwithSort</span><span class="p">(</span><span class="kt">int</span> <span class="n">socre</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">);</span><span class="c1">//</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
   <span class="kt">int</span>   <span class="n">score</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">n</span><span class="p">,</span><span class="n">pos</span><span class="p">;</span>
   <span class="kt">long</span>  <span class="n">num</span><span class="p">[</span><span class="n">N</span><span class="p">],</span><span class="n">x</span><span class="p">;</span>
   <span class="n">n</span><span class="o">=</span><span class="n">ReadScore</span><span class="p">(</span><span class="n">num</span><span class="p">,</span><span class="n">score</span><span class="p">);</span>
   <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Please Input student ID.&quot;</span><span class="p">);</span>
   <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%ld&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">x</span><span class="p">);</span>
   <span class="n">SwithSort</span><span class="p">(</span><span class="n">score</span><span class="p">,</span><span class="n">n</span><span class="p">);</span>
   <span class="c1">//SelectSort(score,n);</span>
   <span class="c1">//BubbleSort(score,n);</span>
   <span class="n">pos</span> <span class="o">=</span><span class="n">lineSearch</span><span class="p">(</span><span class="n">num</span><span class="p">,</span><span class="n">x</span><span class="p">,</span><span class="n">n</span><span class="p">);</span>
   <span class="c1">//pos =BinarySearch(num,x,n);</span>


   <span class="k">if</span><span class="p">(</span><span class="n">pos</span><span class="o">!=-</span><span class="mi">1</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;socre=%d</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">score</span><span class="p">[</span><span class="n">pos</span><span class="p">]);</span>
    <span class="p">}</span>
   <span class="k">else</span>
   <span class="p">{</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Not Found!</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">);</span>
   <span class="p">}</span>

    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">lineSearch</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span><span class="c1">//线性查找</span>
<span class="p">{</span>
    <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">if</span> <span class="p">(</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">==</span><span class="n">x</span><span class="p">)</span>
            <span class="p">{</span>
                <span class="k">return</span> <span class="mi">1</span><span class="p">;</span>
            <span class="p">}</span>
    <span class="p">}</span>
    <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>
<span class="kt">int</span> <span class="nf">ReadScore</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">score</span><span class="p">[])</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span><span class="o">=-</span><span class="mi">1</span><span class="p">;</span>
    <span class="k">do</span>
    <span class="p">{</span>
        <span class="n">i</span><span class="o">++</span><span class="p">;</span>
        <span class="n">printf</span><span class="p">(</span><span class="s">&quot;Input,num,score:&quot;</span> <span class="p">);</span>
        <span class="n">scanf</span><span class="p">(</span><span class="s">&quot;%ld%d&quot;</span><span class="p">,</span><span class="o">&amp;</span><span class="n">num</span><span class="p">[</span><span class="n">i</span><span class="p">],</span><span class="o">&amp;</span><span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">]);</span>
    <span class="p">}</span><span class="k">while</span><span class="p">(</span><span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&gt;=</span><span class="mi">0</span> <span class="o">&amp;&amp;</span> <span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&lt;=</span><span class="mi">100</span><span class="p">);</span>

    <span class="k">return</span> <span class="n">i</span><span class="p">;</span>
<span class="p">}</span>

<span class="kt">int</span> <span class="nf">BinarySearch</span><span class="p">(</span><span class="kt">long</span> <span class="n">num</span><span class="p">[],</span><span class="kt">int</span> <span class="n">x</span><span class="p">,</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span><span class="c1">//假设数组升序排序</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">low</span> <span class="o">=</span> <span class="mi">0</span><span class="p">,</span><span class="n">high</span> <span class="o">=</span> <span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">,</span><span class="n">mid</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">low</span> <span class="o">&lt;=</span><span class="n">high</span><span class="p">)</span><span class="c1">//区间存在</span>
    <span class="p">{</span>
        <span class="n">mid</span><span class="o">=</span><span class="p">(</span><span class="n">high</span><span class="o">+</span><span class="n">low</span><span class="p">)</span><span class="o">/</span><span class="mi">2</span><span class="p">;</span><span class="c1">//mid = low +(high-low)/2;方知数值溢出。分治思想的完美体现</span>
        <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">&gt;</span><span class="n">num</span><span class="p">[</span><span class="n">mid</span><span class="p">])</span>
        <span class="p">{</span>
            <span class="n">low</span><span class="o">=</span><span class="n">mid</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">else</span> <span class="k">if</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;</span><span class="n">num</span><span class="p">[</span><span class="n">mid</span><span class="p">])</span>
        <span class="p">{</span>
            <span class="n">high</span><span class="o">=</span><span class="n">mid</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">else</span>
        <span class="p">{</span>
            <span class="k">return</span> <span class="n">mid</span><span class="p">;</span> <span class="c1">//返回下标位置</span>
        <span class="p">}</span>
    <span class="p">}</span>

    <span class="k">return</span> <span class="o">-</span><span class="mi">1</span><span class="p">;</span>
<span class="p">}</span>


<span class="kt">void</span> <span class="nf">SwithSort</span><span class="p">(</span><span class="kt">int</span> <span class="n">score</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span><span class="c1">//升序排列</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">temp</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
        <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">j</span><span class="o">=</span><span class="n">j</span><span class="o">+</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span><span class="p">(</span><span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">&gt;</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">])</span>
                <span class="n">temp</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">];</span>
                <span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
                <span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">temp</span><span class="p">;</span>
        <span class="p">}</span>
<span class="p">}</span>

<span class="kt">void</span> <span class="nf">SelectSort</span><span class="p">(</span><span class="kt">int</span> <span class="n">score</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">temp</span><span class="p">,</span><span class="n">k</span><span class="p">,</span><span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="o">++</span><span class="n">i</span><span class="p">)</span>
    <span class="p">{</span>
                <span class="n">k</span><span class="o">=</span><span class="n">i</span><span class="p">;</span>
        <span class="k">for</span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="k">if</span><span class="p">(</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">&lt;</span><span class="n">score</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
                <span class="n">k</span><span class="o">=</span><span class="n">j</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">if</span><span class="p">(</span><span class="n">k</span><span class="o">!=</span><span class="n">i</span><span class="p">)</span>
        <span class="p">{</span>
            <span class="n">temp</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">k</span><span class="p">];</span>
            <span class="n">score</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
            <span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">temp</span><span class="p">;</span>
        <span class="p">}</span>
    <span class="p">}</span>       
<span class="p">}</span>


<span class="kt">void</span> <span class="nf">BubbleSort</span><span class="p">(</span><span class="kt">int</span> <span class="n">score</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">)</span>
<span class="p">{</span>
    <span class="kt">int</span> <span class="n">i</span><span class="p">,</span><span class="n">j</span><span class="p">,</span><span class="n">temp</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;</span><span class="n">n</span><span class="o">-</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span>
    <span class="p">{</span>
        <span class="k">for</span><span class="p">(</span><span class="n">j</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">j</span><span class="o">&lt;</span><span class="n">n</span><span class="o">-</span><span class="n">i</span><span class="p">;</span><span class="n">j</span><span class="o">++</span><span class="p">)</span> <span class="c1">//i为已经排好序的元素</span>
        <span class="p">{</span>
            <span class="k">if</span><span class="p">(</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">&lt;</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">])</span><span class="c1">// j从1开始</span>
            <span class="p">{</span>
                <span class="n">temp</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">];</span>
                <span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="p">]</span><span class="o">=</span><span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">];</span>
                <span class="n">score</span><span class="p">[</span><span class="n">j</span><span class="o">-</span><span class="mi">1</span><span class="p">]</span><span class="o">=</span><span class="n">temp</span><span class="p">;</span>
            <span class="p">}</span>
        <span class="p">}</span>
    <span class="p">}</span>
<span class="p">}</span>
</pre></div>
    </div><!-- /.entry-content -->

  </article>
</section>
        <section id="extras" class="body">
                <div class="blogroll">
                        <h2>blogroll</h2>
                        <ul>
                            <li><a href="http://getpelican.com/">Pelican</a></li>
                            <li><a href="http://python.org/">Python.org</a></li>
                            <li><a href="http://jinja.pocoo.org/">Jinja2</a></li>
                            <li><a href="#">You can modify those links in your config file</a></li>
                        </ul>
                </div><!-- /.blogroll -->
                <div class="social">
                        <h2>social</h2>
                        <ul>

                            <li><a href="#">You can add links in your config file</a></li>
                            <li><a href="#">Another social link</a></li>
                        </ul>
                </div><!-- /.social -->
        </section><!-- /#extras -->

        <footer id="contentinfo" class="body">
                <p>Powered by <a href="http://www.maxiaoan.com/">Maxiaoan</a></p>
        </footer><!-- /#contentinfo -->

</body>
</html>